package com.zwj.interview.滑动窗口;

import java.util.HashMap;

/**
 * @Author: Zwj
 * @Date: 2022/2/24 16:21
 *
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
 *
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutation-in-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 一个是否包含另一个的全排列 {

    //判断s中是否存在t的排列
    public boolean checkInclusion(String t, String s) {
        //特殊判断
        if (s.length() < t.length()) {
            return false;
        }
        //用于记录字符串T中每个字符出现的次数，map记录被包含的字符串中的字符出现的次数
        HashMap<Character, Integer> needs = new HashMap<>();
        //用于记录字符串T中每个字符在窗口中出现的次数
        HashMap<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0;
        //用来记录有多少个字符满足了条件，如果说valid和needs.size相同，就说明满足了条件
        int valid = 0;
        while (right < s.length()) {
            char c1 = s.charAt(right);
            //1、不断增加窗口
            if (needs.containsKey(c1)) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1).equals(needs.get(c1))) {
                    valid++;
                }
            }
            right++;
            //窗口中数量大于等于目标字符串的长度时，就要考虑缩小窗口的问题
            while(right-left>=t.length()){
                if(valid==needs.size()){
                    return true;
                }
                char c2 = s.charAt(left);
                left++;
                if (needs.containsKey(c2)) {
                    //这个操作本质就是在缩小窗口，最终维护valid，map的put方法返回的值之前的值
                    window.put(c2, window.getOrDefault(c2, 0) - 1);
                    if (window.get(c2) < needs.get(c2)) {
                        valid--;
                    }
                }

            }
        }
        return false;
    }
}